package qsc.algorithm.horseChessAlgorithm;

import java.awt.*;
import java.util.ArrayList;

/**
 * @auther QiuShangcheng
 * @create 2021/4/28
 * <p>
 * 马踏棋盘算法
 */

public class HorseChess {
    public static void main(String[] args) {
        X = 8;
        Y = 8;
        visited = new boolean[X * Y];
        int row = 1; // 马儿初始位置的行，从1开始编号
        int column = 1; // 马儿初始位置的列，从1开始编号
        // 创建棋盘
        int[][] chessboard = new int[X][Y];

        long start = System.currentTimeMillis();
        horseChessAlgorithm(chessboard, row - 1, column - 1, 1);
        long end = System.currentTimeMillis();
        System.out.println("共耗时: " + (end - start) + " 毫秒");

        // 输出棋盘的最后情况
        for (int[] rows : chessboard) {
            for (int step : rows) {
                System.out.print(step + "\t");
            }
            System.out.println();
        }
        System.out.println(isFinish);

    }

    private static int X;//代表列
    private static int Y;//代表行
    private static boolean[] visited;//记录各个位置是否已被访问
    private static boolean isFinish;//记录马儿是否已经遍历整个棋盘

    /**
     * @param horseChess 棋盘
     * @param x          马儿所在当前列
     * @param y          马儿所在当前行
     * @param step       马儿前进的步数
     */
    public static void horseChessAlgorithm(int[][] horseChess, int x, int y, int step) {
        //设置当前马儿位置的步数
        horseChess[x][y] = step;
        //设置该位置已被马儿踏过
        visited[y * X + x] = true;

        //得到马儿即将要去的位置集合
        ArrayList<Point> nextPoints = next(new Point(x, y));
        //进行非递减排序
        sort(nextPoints);

        while (!nextPoints.isEmpty()) {
            Point curPoint = nextPoints.remove(0);
            if (!visited[curPoint.y * X + curPoint.x]) {
                horseChessAlgorithm(horseChess, curPoint.x, curPoint.y, ++step);
            }

        }

        if (step < X * Y && isFinish == false) {
            visited[y * X + x] = false;
            horseChess[x][y] = 0;
        } else {
            isFinish = true;
        }

    }


    /**
     * 对nextPoints进行非递减排序,方便实现贪心算法
     *
     * @param nextPoints
     * @return
     */
    public static ArrayList<Point> sort(ArrayList<Point> nextPoints) {
        nextPoints.sort((o1, o2) -> {
            return next(o1).size() - next(o2).size();
        });
        return nextPoints;
    }


    /**
     * 功能： 根据当前位置(Point对象)，计算马儿还能走哪些位置(Point)，并放入到一个集合中(ArrayList), 最多有8个位置
     *
     * @param curPoint 当前位置
     * @return
     */
    public static ArrayList<Point> next(Point curPoint) {
        ArrayList<Point> nextPoints = new ArrayList<>();

        Point p = new Point();
        if ((p.x = curPoint.x - 2) >= 0 && (p.y = curPoint.y - 1) >= 0) {
            nextPoints.add(new Point(p));
        }
        if ((p.x = curPoint.x - 1) >= 0 && (p.y = curPoint.y - 2) >= 0) {
            nextPoints.add(new Point(p));
        }
        if ((p.x = curPoint.x + 1) < X && (p.y = curPoint.y - 2) >= 0) {
            nextPoints.add(new Point(p));
        }
        if ((p.x = curPoint.x + 2) < X && (p.y = curPoint.y - 1) >= 0) {
            nextPoints.add(new Point(p));
        }
        if ((p.x = curPoint.x - 2) >= 0 && (p.y = curPoint.y + 1) < Y) {
            nextPoints.add(new Point(p));
        }
        if ((p.x = curPoint.x - 1) >= 0 && (p.y = curPoint.y + 2) < Y) {
            nextPoints.add(new Point(p));
        }
        if ((p.x = curPoint.x + 1) < X && (p.y = curPoint.y + 2) < Y) {
            nextPoints.add(new Point(p));
        }
        if ((p.x = curPoint.x + 2) < X && (p.y = curPoint.y + 1) < Y) {
            nextPoints.add(new Point(p));
        }
        return nextPoints;
    }
}
